\documentclass{beamer}
\usepackage[utf8]{inputenc}
\usepackage{algorithm}
\usepackage{algorithmic}

%%rename algorithmic 
\renewcommand{\algorithmicend}{\textbf{fin}}
\renewcommand{\algorithmicif}{\textbf{si}}
\renewcommand{\algorithmicthen}{\textbf{entonces}}
\renewcommand{\algorithmicelse}{\textbf{de lo contrario}}
\renewcommand{\algorithmicelsif}{\algorithmicelse\ \algorithmicif}
\renewcommand{\algorithmicendif}{\algorithmicend}
\renewcommand{\algorithmicfor}{\textbf{para cada}}
\renewcommand{\algorithmicforall}{\textbf{para cada}}
\renewcommand{\algorithmicdo}{\textbf{hacer}}
\renewcommand{\algorithmicendfor}{\algorithmicend}
\renewcommand{\algorithmicendwhile}{\algorithmicend}
\renewcommand{\algorithmicwhile}{\textbf{mientras}}
\renewcommand{\algorithmicuntil}{\textbf{hasta que se cumpla}}
\renewcommand{\algorithmicrepeat}{\textbf{repetir}}

\usetheme{Warsaw}
%\usecolortheme{seagull}

\setcounter{tocdepth}{2}
\title{Paralelismo Aplicado\\
     A Algoritmos Evolutivos\\
     Para Optimización Multiobjetivo}
\author{Alexis Rodríguez}
\date{2007}
\begin{document}
\begin{frame}
  \titlepage
\end{frame}
\section{Agenda}
\begin{frame}
  \footnotesize
  \tableofcontents
\end{frame}
\section{Motivación}

\begin{frame}

    \begin{itemize}

        \item Los problemas de optimización del mundo real a menudo
              involucran múltiples objetivos.
        
        \item Resolver estos problemas con técnicas deterministas o enumerativas 
              no es factible en la mayoría de los casos.

        \item El paralelismo aplicado a los algoritmos evolutivos mejora
              el rendimiento computacional.

    \end{itemize}

\end{frame}

\section{Introducción}
\subsection{MOP}
\begin{frame}
    
    \textbf{Problema de Optimización Multiobjetivo (MOP)}

    \begin{itemize}
    
        \item En lugar de optimizar una función $\Re \rightarrow \Re$ 
              optimizan una función ${\Re}^n \rightarrow {\Re}^k$
        
        \item Frecuentemente los criterios de optimización son contrapuestos

%        \item La solución de un MOP es un conjunto de soluciones que balancean 
%              la optimización de cada uno de los objetivos

    \end{itemize}


\end{frame}
\subsubsection{Presentación formal del problema}
\begin{frame}

    Encontrar un vector
     $ {x}^{*}
        =   \left[
                \begin{array}{lcr}
                    {x_1}^{*},
                    {x_2}^{*},
                    \cdots,
                    {x_n}^{*}
                \end{array}
            \right]^{T}$  que cumpla

    \begin{eqnarray*}
    g_i({x}^{*}) & \geq 0 & i = 1, \dots, m \\
    h_i({x}^{*}) & \leq 0 & i = 1, \dots, p \\
    \end{eqnarray*}

    \begin{center}
    y optimice el vector función
    $\bar{f}({x}^{*}) = {\left[
              \begin{array}{lcr}
                f_1({x}^{*}),
                f_2({x}^{*}),
                \cdots,
                f_k({x}^{*})
               \end{array}
             \right]}^{T}
    $
    \end{center}

    Se le llama $\Omega$ al conjunto de soluciones que satisfacen las restricciones.    

\end{frame}
\subsubsection{Optimalidad de Pareto}

\begin{frame}
    
    \begin{itemize}
    \item \textbf{Dominación de Pareto:}
    
    {\footnotesize
    Dado un vector $\bar{u}=(u_1, \dots, u_k)$ se dice que domina a $\bar{v}=(v_1,\dots, v_k)$ si y solo si
    $\forall i \in \{ 1,\dots,k \}$ $u_i \leq v_i$ y $\exists i$ $\in$ $i \in \{1,\dots,k\}$ $\backslash$ $u_i < v_i$.}
    
        
    \item  \textbf{Conjunto Óptimo de Pareto:}
    {\footnotesize
    $$P^{*}:=\{ x \in \Omega \backslash \not\exists x^{\prime} \in \Omega \backslash \bar{f}(x^{\prime}) \prec \bar{f}(x) \} $$ }



    \item \textbf{Frente de Pareto:}

    {\footnotesize $$PF^{*}:=\{\vec{u} = F(x) = (f_1(x), \cdots, f_k(x)) \backslash x \in P^{*}\}$$}
    \end{itemize}

\end{frame}

\subsubsection{Métodos de resolución de MOPs}

\begin{frame}

    Existen tres formas de resolución de MOPs:
    \begin{itemize}
        \item Enumerativas
        \item Deterministas
              \begin{itemize}
                \item Basadas en cálculo       
                \item Algoritmos Codiciosos
                \item Hill Climbing
                \item Backtracking
            \end{itemize}
       \item Estocásticas
            \begin{itemize}
                \item Búsqueda Aleatoria
                \item Simulated Annealing
                \item Monte Carlo
                \item Computación Evolutiva
            \end{itemize}


    \end{itemize}

\end{frame}


\subsection{Computación Evolutiva}

\begin{frame}
    
    \textbf{Computación Evolutiva}

    \begin{itemize}
        
        \item Son un conjunto de heurísticas
        \item Modelan el proceso de evolución
        \item Trabajan con una población
        \item Basadas en el concepto de supervivencia del mas apto

    \end{itemize}

\end{frame}

\subsubsection{¿Que es un Algoritmo Evolutivo?}
\begin{frame}
    \textbf{Operadores:}
    \begin{itemize}

        \item Selección
        \item Recombinación
        \item Mutación

    \end{itemize}

    \begin{figure}[h]
        \includegraphics[scale=0.2]{../informe/images/AE-Diagram.png}
    \end{figure}

   
\end{frame}


\subsection{MOEA}
\begin{frame}
   
    Se clasifican según la interacción con el usuario
    \begin{itemize}
        \item a {\it priori}.
             \begin{itemize}
                \item Ordenación.
                \item Combinación lineal.
                \item Combinación no lineal.
            \end{itemize}
        \item progresivas. 
     \item a {\it posteriori}.     
         \begin{itemize}
            \item Muestreo independiente.
            \item Selección de criterio.
            \item Agregación de selección.
            \item Muestreo de Pareto.
        \end{itemize}
    \end{itemize}

\end{frame}
\subsubsection{MOEAs basados en muestreo de Pareto}
\begin{frame}
    
    \textbf{Primera generación (desde 1989 hasta 1998)}
    \begin{itemize}
        \item Rankeo de Pareto como asignación de {\it fitness}.
        \item {\it fitness sharing} para mantener la diversidad.
    \end{itemize}
\end{frame}

\begin{frame}

    \textbf{Segunda generación desde 1998 hasta la actualidad} 
    Se incorpora el elitismo a los MOEA de dos formas:
    \begin{itemize}
        \item a través de la política de reposición $(\mu + \lambda)$.
        \item utilizando una población externa que almacena la soluciones no dominadas.
    \end{itemize}

\end{frame}

\begin{frame}
    \textbf{Non dominated Sorting Genetic Algorithm II (NSGA-II)} Deb et al. (2000) 
    \begin{itemize}
        \item No utiliza una población secundaria.
        \item Incorpora elitismo mediante el uso de la política de reposición $(\mu + \lambda)$.
        \item En lugar de {\it fitness sharing} como en NSGA utiliza un mecanismo de 
             {\it crowding} que no requiere parámetros.
    \end{itemize}
\end{frame}

\subsubsection{Comparación de MOEAs}

\begin{frame}
    \textbf{Avances durante la ``segunda generación''}

    \begin{itemize}
        \item Métricas para medir el desempeño de los MOEA.
        \item Problemas estándar.
        \item Mejoras en el desempeño computacional a través de MOEAs paralelos.
    \end{itemize}

\end{frame}
\subsection{Paralelismo Aplicado a EAs} 

\begin{frame}
    
    \textbf{Modelos de paralelismo en EA:} 
    \begin{itemize}
    
        \item Modelo de grano grueso

        \item Modelo de grano fino

        \item Modelo celular
        
    \end{itemize}

\end{frame}



\section{MOEAs Paralelos}
\begin{frame}
    Se analizaron varios proyectos que involucran MOEAs paralelos
    \begin{itemize} 
        \item \textbf{PNSGAII} Nesmachnow (2004)
        \item \textbf{DEME} Universidad de Málaga (marzo 2006)
        \item \textbf{JMetal} Universidad de Málaga (proyecto aún activo)
    \end{itemize}

\end{frame}


\subsection{Mallba}

\begin{frame}
    \textbf{Mallba} Universidades: Málaga, La Laguna y Politécnica de Catalunya
    \begin{itemize}
        \item Provee una biblioteca de esqueletos de algoritmos para OPs, usando métodos: exactos, heurísticos e híbridos.
        \item Ofrece una interfaz única para cada esqueleto independiente de la plataforma.
        \item Orientada al uso del paralelismo en LAN y en WAN
    \end{itemize}
\end{frame}

\section{MOE {\it framework}}

\subsection{Objetivos}
\begin{frame}
    \textbf{MOE}

    Proveer un entorno de desarrollo completo para MOEAs paralelos

    \begin{itemize}
        \item Simplicidad
        \item Flexibilidad
        \item Ortogonalidad
        \item Performance
    \end{itemize}
\end{frame}
\subsection{Implementación}
\begin{frame}
    \textbf{Características}
    \begin{itemize}
        \item Implementado en ANSI-C++
        \item Basado en mpich
        \item Las herramientas auxiliares son de UNIX
        \item Las métricas fuera de línea se calculan con Octave
    \end{itemize}
\end{frame}

\section{Resultados}
\begin{frame}
    Se realizaron experimentos utilizando los problemas ZDT
    \begin{itemize}
        \item Para comparar el desempeño serial y paralelo de la implementación de NSGA-II.
        \item Para comparar el desempeño computacional de NSGA-II y el entorno de trabajo.
    \end{itemize}
\end{frame}


\subsection{Calidad de las soluciones}
\begin{frame}
    Se realizaron experminetos para comparar los valores de las métricas: cantidad de puntos no-dominados, distancia generacional, {\it spacing} y {\it spread} 
   
    \begin{itemize}
        \item No hay diferencias considerables entre las versiones serial y paralela.
        \item Los resultados son comparables a los obtenidos en PNSGAII.
    \end{itemize}
\end{frame}
\subsection{Desempeño Computacional}

\begin{frame}
    Para medir el desempeño computacional utilizando desde 2 hasta 9 nodos, de forma de poder apreciar la evolución.

    Para ello se utilizaron dos ambientes, uno con 500 generaciones y otro con 1500 generaciones.


\end{frame}

\begin{frame}
    \begin{center}
        \includegraphics[scale=0.35]{../informe/graphs/tiempos_promedio.png}
    \end{center}
\end{frame}


\section{Conclusiones y Trabajo Futuro}
\subsection{Conclusiones}

\begin{frame}
    \begin{itemize}
        \item Se consolida la investigación sobre MOEAs Paralelos en el informe.
        \item Como resultado se implementa un entorno de trabajo.
        \item MOE brinda una interfaz sencilla para el uso de MOEAs Paralelos.
        \item Los resultados de los experimentos  muestran un buen desempeño.
    \end{itemize}
\end{frame}

\subsection{Trabajo Futuro}

\begin{frame}
    \begin{itemize}
        \item Extensiones del {\it framework}.
        \begin{itemize}
            \item MOEAs, operadores y problemas.
            \item Otras técnicas de la computación evolutiva: GA, ES y EPs.
            \item Otros modelos de paralelismo.
        \end{itemize}
        \item Experimentación.
    \end{itemize}
\end{frame}

\begin{frame}

    \begin{center}
    {\huge \tt fin();}
    \end{center}
\end{frame}


\end{document}

